#!/usr/bin/python
# Filename: Tree.py

# Tree and Forest

# Concept:
# Tree is a set of nodes(n): N(n in N), and a set of relationships(r): R(r in R)
# which are the relationships between a pair of nodes.
# if set N is not empty, there must be only n(n0, called root) who don't have a precursor,
# while others have only 1 precursor(parent).
# there is an only path from root to other nodes, in fact, any path between nodes is unique.
# other concept of tree:
# child, sibling, ascendent, descendent, edge, leaf(terminal), branch, degree, level, ordered tree.
# Forest is a set of trees with on intersection.

# Presentation:
# 1) N and R
# 2) tree view
# 3) Venn's diagram
# 4) indentation view
# 5) embedded parenthesis
# 6) binary tree:
# !!!every "ordered" tree or forest can be presented as an unique binary tree.
# Tree
# tree_to_btree(root):
# a) broot = BTree(tree.root.value)
# b) broot.left = tree_to_btree(root.first_child())
# c) curr = broot
# d) while root.right_sibling():
# d.1) curr.right = tree_to_btree(root.right_sibling())
# d.2) curr = curr.right, root = root.right_sibling()
# caution: root does not has a right_child.
# Forest:
# 1) binary tree:
# a) broot = BTree(forest.first_tree().value)
# b) broot.left = tree_to_btree(forest.fisrt_tree())
# c) curr = broot, curr_t = forest.first_tree().next_tree()
# d) while curr_t:
# d.1) curr.right = tree_to_btree(curr_t)
# d.2) curr = curr.right, curr_t = curr_t.next_tree()
# 7) parent reference

# Recursive Defination:
# Tree is a limited set of nodes(n):
# 1) with a node called root
# 2) other nodes are split into m(m>=0) sets with no intersection, each set is a tree
# caution: sets of intersection will lead to generalized list, not tree

# Traversal:
# 1) root first
# 2) root last
# 3) level(width first)
# caution, traversal of forest is from tree to tree,
# so root last traveral can be different from its binary tree presentation.

# Storage:
# 1) child table
# a) a table with 3 column: value, parent, reference to child list.
# this table contains all nodes, and root has no parent.
# b) several child lists, each from the first child to the last.
# 2) left child and right sibling (main method)
# it's a table with 4 column: left child reference, value, parent, right sibling reference.
# this method is just the sequential binary tree presentation.
# 3) dynamic child reference
# nodes of dynamic size which contains value, size and reference to its children.
# when add a child to node, its size increase and a reference is added
# this method is just the tree view presentation.
# 4) parent reference
# it's a table of nodes with parent's reference and value, root has no parent.
# 5) root first sequence with right reference
# this is also a method to present tree with binary tree,
# binary tree can be composed from the sequence.
# it's a table of nodes with value, right sibling reference, tag(if node has no child).
# left(first child) reference can be infered from right reference and tag:
# a) if tag = 1, no child, left reference is None.
# b) if tag = 0, has child, left reference is next node in sequence.
# 6) root first sequence with double tags
# this is also a method to present tree with binary tree,
# binary tree can be composed from the sequence.
# it's a table of nodes with value, ltag(if node has no child), rtag(if node has no right sibling).
# ltag is dealed as tag in root first sequence with right reference.
# rtag is much more complicated:
# a) if rtag = 1, no right sibling.
# b) if rtag = 0, has right sibing, right reference is to be determined.
# b.1) node before right reference(in sequence) must be the rightest node of left child.
# b.2) this node has no child, so its ltag == 1.
# b.3) in left child, situation b can occur many times, so a stack is need.
# b.4) when rtag = 0(above rtag = 0 in b is already pushed in), push.
# b.5) when ltag = 1, pop.
# b.6) when stack is empty, the next node is right reference.
# bcz of the inference, this method is not widely used.
# 7) level order(width first) sequence with left tag
# this is also a method to present tree with binary tree,
# binary tree can be composed from the sequence.
# it's a table of nodes with value, left(first child) reference, tag(if node has no right sibling).
# right sibling reference can be infered from left reference and tag:
# a) if tag = 1, no right sibling, right sibling reference is None.
# b) if tag = 0, has right sibling, right sibling reference is next node in sequence.
# 8) root last sequence with degree
# this is also a method to present tree with binary tree,
# binary tree can be composed from the sequence.
# it's a table of nodes with value, degree.
# pre-node in sequence is the last child of node
# stack.push(last node in sequence)
# while not (stack.size == 1 and stack.top.degree == 0):
# a) if stack.top.degree != 0:
# a.1) stack.push(pre node in sequence)
# b) elif stack.top.degree == 0:
# b.0) node = stack.pop()
# b.1) stack.top.add_before_last_child(node)
# b.2) stack.top.degree -= 1
# root = stack.pop()
# 9) root first sequence with degree
# 10) level order(width first) sequence with degree

# Abstract Data Type:
# using "left child and right sibling" binary tree to present tree
